/**********************************************************

@description: weight must bigger than 0, and when init, lchid=-1,rchild=-1
*File Name:huffmanTree.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Wed 30 Apr 2025 05:33:28 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 256
typedef struct tnode{
	int weight,parent,lchild,rchild;
}tnode;

typedef struct HFMTree{
	tnode* data;
	int length;
}HFMTree;

void init_node(tnode * node,int weight){
	node->weight=weight;
	node->parent=0;
	node->lchild=-1;
	node->rchild=-1;
}
void swap(int *weight,int i,int j){
	if(i==j)
		return;
	int tmp=*(weight+i);
	*(weight+i)=*(weight+j);
	*(weight+j)=tmp;
}
void sort(int *weight,int length){
	int i=0,j=0;
	for(i=0;i<length;i++){
		for(j=1;j<length-i;j++){
			if(*(weight+j-1)>*(weight+j)){
				swap(weight,j-1,j);
			}
		}
	}
}
//the weight must be in sorted form
HFMTree * initTree(int *weight,int length){
	HFMTree * t=(HFMTree*)malloc(sizeof(HFMTree));
	t->data=(tnode*)malloc(sizeof(tnode)*(2*length-1));
	t->length=length;
	for(int i=0;i<length;i++){
		init_node(&t->data[i],*(weight+i));
	}
	return t;
}
int* selectMin(HFMTree *t){
	int min0=10000,min1=10000;
	int min0Idx,min1Idx;
	for(int i=0;i<t->length;i++){
		if(t->data[i].parent==0){
			if(t->data[i].weight<min0){
				min0=t->data[i].weight;
				min0Idx=i;
			}
		}
	}
	for(int i=0;i<t->length;i++){
		if(t->data[i].parent==0){
			if(t->data[i].weight<min1 && i!=min0Idx){
				min1=t->data[i].weight;
				min1Idx=i;
			}
		}
	}
	int* ret=(int*)malloc(sizeof(int)*2);
	ret[0]=min0Idx;
	ret[1]=min1Idx;
	return ret;
}
void createHFMTree(HFMTree *t){
	int *res;
	int min0Idx,min1Idx;
	int treeSize=t->length*2-1;
	for(int i=t->length;i<treeSize;i++){
		res=selectMin(t);
		min0Idx=res[0];
		min1Idx=res[1];
		t->data[i].weight=t->data[min0Idx].weight+t->data[min1Idx].weight;
		t->data[i].lchild=min0Idx;
		t->data[i].rchild=min1Idx;
		t->data[i].parent=0;
		t->data[min0Idx].parent=i;
		t->data[min1Idx].parent=i;
		t->length++;
	}
}
void preorder(HFMTree *t,int index){
	if(index !=-1){
		printf("%d ",t->data[index].weight);
		preorder(t,t->data[index].lchild);
		preorder(t,t->data[index].rchild);
	}
}
int main(){
//	int weight[5]={5,4,3,2,1};
//	sort(weight,5);
    //int weight[4]={1,2,3,4};
    int weight[7]={5,1,3,6,11,2,4};
	for(int i=0;i<7;i++){
		printf("%d ",weight[i]);
	}
	printf("\n");
	HFMTree *t=initTree(weight,7);
	for(int i=0;i<7;i++){
		printf("%d ",t->data[i].weight);
	}
	printf("\n");
	int *minArr=selectMin(t);
	printf("min[0]=%d,min[1]=%d\n",minArr[0],minArr[1]);
	createHFMTree(t);
	preorder(t,t->length-1);
}
